import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-09-15
 * Time: 0:03
 */

//方法二:使用哈希表并且不维护有效字符：
public class Method2 {
    static Map<Character, Integer> hash1 = new HashMap<Character, Integer>();
    static Map<Character, Integer> hash2 = new HashMap<Character, Integer>();

    public static String minWindow(String ss, String tt) {


        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        for(char ch : t)
            hash1.put(ch,hash1.getOrDefault(ch,0) + 1);

        int begin = -1;//返回变量
        int minlen = Integer.MAX_VALUE;

        for(int left = 0, right = 0, count = 0/* 注意count维护有效字符的种类 **/; right < s.length; right++) {
            //进窗口
            hash2.put(s[right],hash2.getOrDefault(s[right],0) + 1);

            while(check()){

                //更新
                if(minlen > right-left+1){
                    begin = left;
                    minlen = right - left + 1;
                }

                //出窗口
                hash2.put(s[left],hash2.getOrDefault(s[left],0) - 1);
                left++;
            }

        }

        if(begin == -1) return new String();
        return ss.substring(begin,begin + minlen);
    }

    public static boolean check() {
        Iterator iter = hash1.entrySet().iterator();
        while (iter.hasNext()) {

            //Entry对象和Node对象是一个节点，让构造器去遍历，每一个节点
            Map.Entry entry = (Map.Entry) iter.next();


            //获得entry对象的key和val并比较
            Character key = (Character) entry.getKey();
            Integer val = (Integer) entry.getValue();
            if (hash2.getOrDefault(key, 0) < val) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        String minWindow = minWindow(s,t);
        System.out.println(minWindow);
    }
}
